﻿#pragma once
#include<vector>
#include<iostream>
#include<string>
using namespace std;
 
 //using namespace std;
 //namespace H
 //{
	// enum state
	// {
	//	 EMPTY,
	//	 EXIST, 
	//	 DELETE
	// };

	// template<class K, class V>
	// struct HashData
	// {
	//	 pair<K, V> _kv;
	//	 state _sta = EMPTY;
	// };

	// template<class K>
	// struct HashFunc
	// {
	//	 size_t operator()(const K& data)
	//	 {
	//		 return (size_t)data;
	//	 }
	// };

	// template<>
	// struct HashFunc<string>
	// {
	//	 size_t operator()(const string& data)
	//	 {
	//		 size_t ret = 0;
	//		 for (auto e : data)
	//		 {
	//			 ret *= 131;
	//			 ret += e;
	//		 }
	//		 return ret;
	//	 }
	// };



	// template<class K, class V, class Hash = HashFunc<K>>
	// class HashTable
	// {
	// public:
	//	 inline unsigned long __stl_next_prime(unsigned long n)
	//	 {
	//		 // Note: assumes long is at least 32 bits.
	//		 static const int __stl_num_primes = 28;
	//		 static const unsigned long __stl_prime_list[__stl_num_primes] =
	//		 {
	//			 53, 97, 193, 389, 769,
	//			1543, 3079, 6151, 12289, 24593,
	//			49157, 98317, 196613, 393241, 786433,
	//			1572869, 3145739, 6291469, 12582917, 25165843,
	//			50331653, 100663319, 201326611, 402653189, 805306457,
	//			1610612741, 3221225473, 4294967291
	//		 };
	//		 const unsigned long* first = __stl_prime_list;
	//		 const unsigned long* last = __stl_prime_list +
	//			 __stl_num_primes;
	//		 const unsigned long* pos = lower_bound(first, last, n);
	//		 return pos == last ? *(last - 1) : *pos;
	//	 }

	//	 bool Insert(const pair<K, V>& kv)
	//	 {
	//		 //先查找在不在
	//		 if (Find(kv.first) != nullptr)
	//			 return false;

	//		 size_t M = _tables.size();
	//		 if (M == 0 || _n * 10 / M >= 7)
	//		 {
	//			 //扩容
	//			 /*vector<HashData<K, V>> tmp;
	//			 tmp.resize(M ? 2 * M : 11);				 
	//			 for (int i = 0; i < M; ++i)
	//			 {
	//				 if (_tables[i]._sta == EXIST)
	//				 {
	//					 int hashi = _tables[i]._kv.first % (2 * M);
	//					 int j = 1;
	//					 while (tmp[hashi]._sta != EMPTY)
	//					 {
	//						 hashi = (hashi + j) % (2 * M);
	//						 ++j;
	//					 }
	//					 tmp[hashi]._kv = kv;
	//					 tmp[hashi]._sta = EXIST;
	//				 }
	//			 }
	//			 swap(tmp, _tables);
	//			 M = _tables.size();*/

	//			 HashTable<K, V> tmp;
	//			 //tmp._tables.resize(M ? 2 * M : 11);
	//			 tmp._tables.resize(__stl_next_prime(M));

	//			 for (int i = 0; i < M; ++i)
	//			 {
	//				 if (_tables[i]._sta == EXIST)
	//				 {
	//					 tmp.Insert(_tables[i]._kv);
	//				 }
	//			 }
	//			 _tables.swap(tmp._tables);
	//			 M = _tables.size();
	//		 }

	//		 //插入
	//		 //int hashi = kv.first % M;
	//		 size_t hashi = Hash()(kv.first) % M;
	//		 int i = 1;
	//		 while (_tables[hashi]._sta != EMPTY)
	//		 {
	//			 hashi = (hashi + i) % M;
	//			 ++i;
	//		 }
	//		 _tables[hashi]._kv = kv;
	//		 _tables[hashi]._sta = EXIST;
	//		 ++_n;

	//		 return true;
	//	 }


	//	 HashData<K, V>* Find(const K& key)
	//	 {
	//		 if (!_tables.size())
	//			 return nullptr;
	//		 int hashi = Hash()(key) % _tables.size();
	//		 int i = 1;
	//		 while (_tables[hashi]._sta != EMPTY)
	//		 {
	//			 //if (_tables[hashi]._kv.first == key)
	//			 if(_tables[hashi]._kv.first == key && _tables[hashi]._sta == EXIST)
	//				 return &_tables[hashi];
	//			 
	//				++i;
	//				hashi = (hashi + i) % _tables.size();
	//		 }
	//		 return nullptr;
	//	 }

	//	 bool Erase(const K& key)
	//	 {
	//		 HashData<K, V>* ret = Find(key);
	//		 if (ret == nullptr)
	//			 return false;
	//		 
	//		 ret->_sta = DELETE;
	//		 --_n;
	//		 return true;
	//	 }
	// private:
	//	 vector<HashData<K, V>> _tables;
	//	 size_t _n = 0;
	// };
 //}



	 
template<class T>
struct HashNode
{
	T _data;
	HashNode* _next ;

	HashNode(const T& data)
		:_data(data)
		,_next(nullptr)
	{}
};

template<class K>
struct HashFunc
{
	size_t operator()(const K& data)
	{
		return (size_t)data;
	}
};

template<>
struct HashFunc<string>
{
	size_t operator()(const string& data)
	{
		size_t ret = 0;
		for (auto e : data)
		{
			ret *= 131;
			ret += e;
		}
		return ret;
	}
};


template<class K, class T, class KeyOfT, class Hash>
class HashTable;


template<class K, class T, class KeyOfT, class Hash, class Ref, class Ptr>
class HashTableIterator
{
	typedef HashNode<T> Node;
	typedef HashTableIterator<K, T, KeyOfT, Hash, Ref, Ptr> Self;
	typedef HashTable<K, T, KeyOfT, Hash> HT;

public:
	HashTableIterator(Node* node, HT* ht)
		: _node(node)
		, _ht(ht)
	{}

	Ref operator*() const
	{
		return _node->_data;
	}

	Ptr operator->() const
	{
		return &(_node->_data);
	}

	bool operator==(const Self& self) const
	{
		return _node == self._node;
	}

	bool operator!=(const Self& self) const
	{
		return _node != self._node;
	}

	//错误版本，返回值是Self&，同时如果创建一个新的对象返回，我们的it要接受：it = ++it
	//封装map和set时已经说过这个问题了
	/*Self operator++()
	{
		if (_node->_next)
		{
			return { _node->_next, _ht };
		}

		int hashi = Hash()(KeyOfT()(_node->_data)) % _ht->_tables.size();
		for (int i = hashi + 1; i < _ht->_tables.size(); ++i)
		{
			if (_ht->_tables[i])
			{
				return { _ht->_tables[i] , _ht };
			}
		}

		return { nullptr, _ht };
	}*/

	Self& operator++()
	{
		if (_node->_next)
		{
			//return { _node->_next, _ht };
			_node = _node->_next;
			return *this;
		}

		int hashi = Hash()(KeyOfT()(_node->_data)) % _ht->_tables.size();
		for (int i = hashi + 1; i < _ht->_tables.size(); ++i)
		{
			if (_ht->_tables[i])
			{
				//return { _ht->_tables[i] , _ht };
				_node = _ht->_tables[i];
				return *this;
			}
		}

		//return { nullptr, _ht };
		_node = nullptr;
		return *this;
	}

	Node* _node;
	HT* _ht;
};

template<class K, class T, class KeyOfT,  class Hash>
class HashTable
{
	typedef HashNode<T> Node;
	template<class K, class T, class KeyOfT, class Hash, class Ref, class Ptr>
	friend class HashTableIterator;
public:
	typedef HashTableIterator<K, T, KeyOfT, Hash, T&, T*> Iterator;
	typedef HashTableIterator<K, T, KeyOfT, Hash, const T&, const T*> ConstIterator;

		
	HashTable()
		:_tables(11)
		,_n(0)
	{}

	~HashTable()
	{
		for (auto i : _tables)
		{
			if(i)
			{
				Node* cur = i;
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				i = nullptr;
			}

		}
	}

	Iterator Begin()
	{
		for (int i = 0; i < _tables.size(); ++i)
		{
			if (_tables[i])
				return { _tables[i], this };
		}
		return { nullptr, this };
	}

	ConstIterator Begin() const
	{
		for (int i = 0; i < _tables.size(); ++i)
		{
			if (_tables[i])
				return { _tables[i], this };
		}
		return { nullptr, this };
	}

	Iterator End()
	{
		return { nullptr, this };
	}

	ConstIterator End() const
	{
		return { nullptr, this };
	}

	inline unsigned long __stl_next_prime(unsigned long n)
	{
		// Note: assumes long is at least 32 bits.
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
			53, 97, 193, 389, 769,
			1543, 3079, 6151, 12289, 24593,
			49157, 98317, 196613, 393241, 786433,
			1572869, 3145739, 6291469, 12582917, 25165843,
			50331653, 100663319, 201326611, 402653189, 805306457,
			1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list +
			__stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}

	pair<Iterator, bool> Insert(const T& data)
	{
		//先查找在不在
		if (Find(KeyOfT()(data)) != End())
			return { {nullptr, this} , false };

		if (_n / _tables.size() == 10)
		{
			vector<Node*> new_tables;
			new_tables.resize(__stl_next_prime(_tables.size()));
			typename vector<Node*>::iterator it = _tables.begin();
			while (it != _tables.end())
			{
				if (*it)
				{
					Node* cur = *it;
					while (cur)
					{
						/*size_t hashi = Hash()(KeyOfT()(cur)) % new_tables.size();
						Node* tmp = new Node(cur->_data);

						Node* cur0 = new_tables[hashi];
						new_tables[hashi] = tmp;
						tmp->_next = cur0;*/

						size_t hashi = Hash()(KeyOfT()(cur->_data)) % new_tables.size();
						Node* next = cur->_next;

						Node* newcur = new_tables[hashi];
						new_tables[hashi] = cur;
						cur->_next = newcur;
							
						cur = next;
					}
					*it = nullptr;
				}
				++it;
			}
			_tables.swap(new_tables);
		}

		size_t hashi = Hash()(KeyOfT()(data)) % _tables.size();
		Node* tmp = new Node(data);

		Node* cur = _tables[hashi];
		_tables[hashi] = tmp;
		tmp->_next = cur;
		++_n;

		return { {_tables[hashi], this}, true };
	}


	Iterator Find(const K& key)
	{
		if (!_tables.size())
			return {nullptr, this};

		int hashi = Hash()(key) % _tables.size();

		Node* cur = _tables[hashi];
		while (cur)
		{
			if (KeyOfT()(cur->_data) == key)
				return {cur, this};
			cur = cur->_next;
		}
		return { nullptr, this };
	}

	int Size()
	{
		return _n;
	}

	bool Erase(const K& key)
	{
		if (!_tables.size())
			return false;

		int hashi = Hash()(key) % _tables.size();

		if (!_tables[hashi])
			return false;

		if (KeyOfT()(_tables[hashi]->_data) == key)
		{		
			delete _tables[hashi];
			_tables[hashi] = nullptr;
			return true;
		}
			
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (KeyOfT()(cur->_next->_data) == key)
			{
				Node* tmp = cur->_next->_next;
				delete cur->_next;
				cur->_next = tmp;
				return true;
			}
			cur = cur->_next;
		}
		return false;	 
	}

private:
	vector<Node*> _tables;
	size_t _n = 0;
};



